This program calculates 2-dimensional Discrete Fourier Transforms (DFTs) of images saved as a Photoshop 2.0 file. 2d Fourier transforms, or, in more common words, image 'spectra', can be used to filter images in ways not possible with ordinary filters. Note that mathematically, the Fourier transform is 'lossless': the transformed image contains *exactly* the same information than the original - it is merely represented in a different way. The original can therefore be fully recovered from the transformed image, even though the transform may look quite awkward to the human eye.
This document is not intended to teach you digital image processing. There are many books available on the subject. I tried, however, to keep the text on such a level that anyone with a bit of mathematical feeling should be able to understand the bearing of the Fourier transform.
A Fourier transformed image consists of the spectral components of the original image. Like a sound is built up from many waves with their individual frequencies, an image can be seen as built up from a set of interfering waves. These waves are exactly like waves on water: their frequency is measured with a "number of waves per unit distance". The higher the frequency of the wave, the more detail it represents in the original image and the further away from the frequency origin it will appear as a spectral amplitude in the transformed image. All these different waves with their different frequencies and relative phases interfere in such a way that they exactly build up the original image, like a still photograph of a water basin.
A transformed image contains complex data. For those of you not familiar with the mathematics of complex numbers: a complex number is an extension to a real number (e.g. ╣). It has a real part (which we're all familiar with) and an additional imaginary part. Together, they allow you to easily define and handle the harmonics that are extracted from the image. They are an essential part of digital signal and image processing and in particular, the Fourier transform, although it is not necessary to know the mathematics of complex numbers in order to be able to use this program. This is possible because this application outputs the complex numbers in an easy to understand form: an absolute value (the 'strength' of a spectral component or 'amplitude' of the wave) and a phase (that you usually don't have to (or want to) work with). The amplitude and phase of the transformed image appear in separate channels of the Photoshop file, allowing you to edit only the amplitude part.
Transformed (and possibly edited) images may of course be transformed back to a normal image (so-called Inverse Fourier Transform).
Example: descreening of an image
Suppose you have an image that suffers severely from screening, like the example file 'ki-small' (It may be a good idea at this point to open all four example files in Photoshop). In the transform, shown in the file 'ki-small.fft', the screening 'grid' shows up as 4 discrete spectral peaks, easily identifiable from the rest of the image.
The transform has its origin located halfway the bottom side of the image. This point (0,0) is the spectral component with zero frequency, or the overall grayness of the picture. Spectral components away from this origin have a frequency that is measured by their distance to the origin The direction of the waves they represent is measured from the origin as well.
It is possible to eliminate the anomalies in 'ki-small.fft' by reducing their stength with the rubber stamp tool while the brush mode is set at 'Darken'. With this brush, the anomaly is made to look like its surroundings so it no longer sticks out. The result is shown in the file 'ki-small.fft.corrected'. Once this file is transformed back (with 'Inverse FFT' in the program options dialog), the screening has completely gone (Photoshop file 'ki-small.corrected.ift'). Notice the selectivity of the method: almost no detail has suffered from the filtering. Even the thin horizonal fault lines, that are also present in the original, are not affected. Nor are the square blocks due to the JPEG compression of the original image affected in any way. This is easily explained: A widely used method, like blurring, would have reduced the amplitude of *all* freqency components in *every* direction outside a circle of a given radius (in the ideal case, the radius being just inside the four anomalous peaks). Many frequency components that build up the details of this image, would then have been lost.
Simple exercise: blurring in frequency space
Take the file 'ki-small.fft' and select with the circle selection tool (double click) a circle with diameter 64 pixels. Place this circle with its centre halfway the bottom side of the image, so that a demi-circle remains. Select the inverse area and fill this with black. Save the image under a different name. Now you have deleted *all* frequency components with frequency > 32/128pixels. Inverse FFT this image. It will appear blurred: You have applied a lowpass filter with a very sharp cut-off frequency.
Repeat this procedure with the contents of the circle blotted out black and the rest still intact. This is a highpass filter.
Application specifics:
* Input:
Photoshop files saved in 2.0 format, in Grayscale, RGB color or Multichannel mode.
* Output:
Photoshop file in 2.0 format of the same mode.
* Input/Output notes:
Forward FFT: The transform output has twice as many channels as the input file (number of channels is N│1 for Grayscale, N│3 for RGB color and N▓8 for Multichannel); the first N channels are filled with the amplitude of the spectral component, the second N channels (N+1▓n▓2N) contain the phase of the spectral component (e.g. (Red,Green,Blue) -> (absRed,absGreen,absBlue, phaseRed,phaseGreen,phaseBlue)).
Inverse FFT: The inverse transform output has half the number of channels as the input (which should be a spectral file - the user should keep track of this, although spectral files are given the extension .fft whereas inverse-transformed files (normal images) are given the extension .ift). The usual absolute-value/phase channel ordering which was output by the Forward Transform is assumed as input for the Inverse Transform.
* Interface:
'Drag-and-Drop'ping Photoshop file(s) onto the 2d-FFT icon is allowed. The application is background-aware to allow lengthy transforms be processed in the background.
The Program Options dialog allows you to select the direction of the transformation: Forward or Inverse (a best guess is made by the program at startup, so you'll rarely need to change this setting). Checking the 'Delete input file when ready' check box will do just that as soon as the image is successfully transformed. This can be used to save disk space when a large number of files have to be transformed (batch mode).
* Algorithm:
The program uses the 2-dimensional version of the FFT (Fast Fourier Transform) algorithm, optimized for this particular use. Since the FFT works only on data sets with a size that is a power of 2 (32, 64, 128 etc.), the horizontal and vertical image sizes are rounded up to the nearest power of two. For instance, a 109x190 image will be Fourier-transformed in an internal 128x256 placeholder.
Since the input data set contains only real data, a symmetry (point-symmetry, actually) in the transformed image allows us to discard half of the transformed data. The amount of information is kept constant by this method: For each input channel, a phase channel is added, but all output channels are half the size. Note that the output file may be bigger than the input file altogether if the input image size was just a little bit larger than a power of 2.
Scaling: the amplitudes are scaled logarithmically due to the extremly large dynamic range of spectral components; the phase simply is mapped from the [-╣,╣] range to [0,255] (phase 0 maps to 128).
* Accuracy:
Although the first paragraph of this release note states that the DFT is 'lossless', some differences may be observed when an image is transformed and back. This is due to the numerical errors that accumulate during the calculation, especially when the output values are rounded off into the limited dynamic range of an 8-bit number. Typically, the numerical error is1.4 on a scale of 255 (0.5%).
* Memory Requirements:
Transforming images of 1024 pixels squared requires a little over 8 MB of memory (the exact amount is indicated by the program, if not sufficient) and scales linearly with image area. Due to the nature of the algorithm, it is not possible to transform the images in independent bands. The image has to be kept in memory in its entirety. Future versions of this program will use a swap file to hold the intermediate results if not enough real RAM is available.
* Performance:
The CPU time needed for a single channel of 1024 pixels squared (approx.):
- 4 min on a Quadra 700 (25 MHz 68040)
- 20 min on a Mac IIcx (16 MHz 68030/68882)
- 26 min on a Mac II (16 MHz 68020/68881)
- 27 min on a Mac LCII (16 MHz 68LC030/third party 68882)
- ages on a Mac LCII (16 MHz 68LC030/noFPU) with SoftwareFPU
CPU time approximately scales linearly with image area.
* System Requirements:
System software 7.0 or higher. Color QuickDraw. Photoshop 2.5 recommended for multi-channel image editing. Floating Point Coprocessor (68881, 68882, 68040) or SoftwareFPU (it works, but is extremely slow). Does not work on a standard Centris 610/650 and Quadra 610: they have an 68LC040 that has no FPU.
